/*
https://leetcode-cn.com/problems/sort-items-by-groups-respecting-dependencies/solution/1203-xiang-mu-guan-li-by-leetcode-t63b/
 */
import java.util.*;

public class Solution1203 {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        for (int i=0;i<group.length;i++){
            if (group[i]==-1){
                group[i]=m;
                m++;
            }
        }
        int[] first=new int[m];
        Arrays.fill(first,-1);
        int[] du=new int[m];
        List<Integer> next=new ArrayList<>();
        List<Integer> go=new ArrayList<>();
        for (int i=0;i<group.length;i++){
            List<Integer> list=beforeItems.get(i);
            for (int j=0;j<list.size();j++){
                if (group[i]!=group[list.get(j)]){
                    next.add(first[group[list.get(j)]]);
                    go.add(group[i]);
                    du[group[i]]++;
                    first[group[list.get(j)]]=next.size()-1;
                }
            }
        }
        List<Integer> l1=topo(first,next,go,du,m);
        if (l1==null){
            return new int[0];
        }
        first=new int[n];
        Arrays.fill(first,-1);
        du=new int[n];
        next.clear();
        go.clear();
        for (int i=0;i<group.length;i++){
            List<Integer> list=beforeItems.get(i);
            for (int j=0;j<list.size();j++){
                next.add(first[list.get(j)]);
                go.add(i);
                du[i]++;
                first[list.get(j)]=next.size()-1;
            }
        }
        List<Integer> l2=topo(first,next,go,du,n);
        if (l2==null){
            return new int[0];
        }
        List<Integer>[] lists=new List[m];
        for (int i=0;i<lists.length;i++){
            lists[i]=new ArrayList<>();
        }
        for (Integer integer : l2) {
            lists[group[integer]].add(integer);
        }
        int[] ans=new int[n];
        int count=0;
        for (Integer integer : l1) {
            List<Integer> list=lists[integer];
            for (Integer integer1 : list) {
                ans[count]=integer1;
                count++;
            }
        }
        return ans;
    }

    List<Integer> topo(int[] first,List<Integer> next,List<Integer> go,int[] du,int t){
        Queue<Integer> queue=new LinkedList<>();
        for (int i=0;i<t;i++){
            if (du[i]==0){
                queue.offer(i);
            }
        }
        List<Integer> ans=new ArrayList<>();
        while (!queue.isEmpty()){
            int p=queue.poll();
            ans.add(p);
            int k=first[p];
            while (k!=-1){
                du[go.get(k)]--;
                if (du[go.get(k)]==0){
                    queue.offer(go.get(k));
                }
                k=next.get(k);
            }
        }
        if (ans.size()!=t){
            return null;
        }else{
            return ans;
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> lists=new ArrayList<>();
        lists.add(new ArrayList<>());
        List<Integer> l1=new ArrayList<>();
        l1.add(6);lists.add(l1);
        List<Integer> l2=new ArrayList<>();
        l2.add(5);lists.add(l2);
        List<Integer> l3=new ArrayList<>();
        l3.add(6);lists.add(l3);
        List<Integer> l4=new ArrayList<>();
        l4.add(3);l4.add(6);lists.add(l4);
        lists.add(new ArrayList<>());
        lists.add(new ArrayList<>());
        lists.add(new ArrayList<>());
        System.out.println(Arrays.toString(new Solution1203().sortItems(8,2,new int[]{-1,-1,1,0,0,1,0,-1},lists)));
    }
}
